package com.example.algorithm.huawei_rongyao_29;

import java.util.Scanner;

// 数组的partition调整补充问题
/**
 * 标题：数组的partition调整补充问题 | 时间限制：2秒 | 内存限制：262144K
 * 给定一个数组arr，其中只可能含有0、1、2三个值，请实现arr的排序
 * 输入描述:
 * 第一行一个整数N。表示数组长度
 * 接下来一行N个整数表示数组内的数
 * 输出描述:
 * 输出N个整数，表示排序后的结果
 *
 * 这个问题可以使用荷兰国旗问题的思想来解决。荷兰国旗问题是关于排序0、1、2三个元素的问题，可以在一次遍历内完成排序。
 * 具体做法是使用三个指针，分别指向当前已经排序好的0的最右边界、1的最右边界和2的最左边界。
 * 然后遍历数组，根据当前元素的值将其放置在对应的位置。
 *
 * 这个程序首先读取输入的数组，并使用一次遍历的方式调用 sortColors 函数对数组进行排序。
 * 在 sortColors 函数中，通过三个指针 left、right 和 i 遍历数组，根据当前元素的值将其放置在对应的位置。
 *
 * */
public class Q04_SortColors {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt(); // 数组长度
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = scanner.nextInt();
        }
        sortColors(arr);
        // 下面只是循环打印出结果而已
        for (int num : arr) {
            System.out.print(num + " ");
        }
        scanner.close();
    }

    // 核心逻辑
    public static void sortColors(int[] arr) {
        int left = 0; // 0的最右边界
        int right = arr.length - 1; // 2的最左边界
        int i = 0; // 遍历指针
        while (i <= right) {
            if (arr[i] == 0) {
                swap(arr, i, left);
                left++;
                i++;
            } else if (arr[i] == 2) {
                swap(arr, i, right);
                right--;
            } else {
                i++;
            }
        }
    }

    public static void swap(int[] arr, int i, int j) {
        // 其实就是交换i和j位置上的数组的值
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
